package LinkList;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: LinkList
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-23  08:23
 * @Description: TODO
 * @Version: 1.0
 */
public class 环形链表II142 {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 表示有环状
            if (fast == slow) {
                // 开始查找环的入口的位置
                ListNode result = head;
                while (result != slow) {
                    result = result.next;
                    slow = slow.next;
                }
                return result;
            }
        }
        return null;
    }
}
